package com.test.daily.leetcode.y2022.m05.day0523.v01;

import java.util.ArrayList;
import java.util.List;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/5/23 上午 07:12
 * @version: 1.0
 */
public class Solution {
    public static class Node{
        int value;
        Node left;
        Node right;
        public Node(int value){
            this.value = value;
        }
    }
    public static boolean isCBT1(Node root){
//        boolean ans = true;
        ArrayList<Integer> list = new ArrayList<>();
        in(root, list);
        for(int i = 0; i < list.size()-1; i++){
            if(list.get(i) > list.get(i+1)){
                return false;
            }
        }
        return true;
    }
    public static void in(Node root, ArrayList<Integer> arrayList){
        if(root == null){
            return;
        }
        in(root.left, arrayList);
        arrayList.add(root.value);
        in(root.right, arrayList);
    }
    public static class Info{
        boolean isCBT;
        int max;
        int min;
        public Info(boolean isCBT, int max, int min){
            this.isCBT = isCBT;
            this.max = max;
            this.min = min;
        }
    }
    public boolean isCBT2(Node root){
        if(root == null){
            return true;
        }
        return process(root).isCBT;
    }
    public Info process(Node root){
        if(root == null){
            return null;
        }
        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);
        int min = root.value;
        int max = root.value;
        if(leftInfo != null){
            max = Math.max(max, leftInfo.max);
            min = Math.min(min, leftInfo.min);
        }
        if(rightInfo != null){
            max= Math.max(max, rightInfo.max);
            min = Math.min(min, rightInfo.min);
        }
        boolean isCBT = true;
        if(leftInfo != null && (!leftInfo.isCBT||leftInfo.max > root.value)){
            isCBT = false;
        }
        if(rightInfo != null && (!rightInfo.isCBT || rightInfo.min < root.value)){
            isCBT = false;
        }
        return new Info(isCBT,max, min);
    }
}
